CM11 链表分割
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

哨兵位
小的就后插
大的就后插
链接
释放空间
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        struct ListNode*lesshead,*lesstail,*greathead,*greattail;
        lesshead=lesstail=(ListNode*)malloc(sizeof(ListNode));
        greathead=greattail=(ListNode*)malloc(sizeof(ListNode));
        struct ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lesstail->next=cur;
                lesstail=lesstail->next;
            }
            else 
            {
                greattail->next=cur;
                greattail=greattail->next;
            }

            cur=cur->next;
        }
        lesstail->next=greathead->next;
        
        greattail->next=NULL;
        pHead=lesshead->next;
        
        free(lesshead);
    
        free(greathead);

        return pHead;
        // write code here
    }
};